#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

// https://leetcode.cn/problems/making-a-large-island/
// 827. 

class Solution
{
public:
    // 深度优先搜索
    void dfs(vector<vector<int>> &grid, int i, int j, int seqNumber)
    {
        if (i < 0 || i >= row || j < 0 || j >= col || grid[i][j] != 1)
        {
            return;
        }
        grid[i][j] = seqNumber;
        for (auto it : remove)
        {
            dfs(grid, i + it.first, j + it.second, seqNumber);
        }
    }
    int largestIsland(vector<vector<int>> &grid)
    {
        row = grid.size();
        col = grid[0].size();
        unordered_map<int, int> recordArea;
        int seqNumber = 2;

        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (grid[i][j] == 1)
                {
                    dfs(grid, i, j, seqNumber);
                    ++seqNumber;
                }
                ++recordArea[grid[i][j]];
            }
        }

        int ans = 0;
        for (auto it : recordArea)
        {
            // cout << "first" << it.first << " ";
            // cout << it.second << endl;
            if (it.first != 0)
            {
                ans = max(ans, it.second);
            }
        }
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (grid[i][j] == 0)
                {
                    position.clear();
                    for (auto it : remove)
                    {
                        int tempi = i;
                        int tempj = j;
                        tempi += it.first;
                        tempj += it.second;
                        if (tempi < 0 || tempi >= row || tempj < 0 || tempj >= col || grid[tempi][tempj] == 0)
                        {
                            continue;
                        }
                        
                        position.insert(grid[tempi][tempj]);
                    }
                    int sum = 1;
                    if (position.size() != 0)
                    {
                        for (int ret : position)
                        {
                            // cout << "ret" << ret << endl;
                            sum += recordArea[ret];
                        }
                    }
                    ans = max(ans, sum);
                }
            }
        }
        return ans;
    }

private:
    int row = 0;
    int col = 0;
    vector<pair<int, int>> remove{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    unordered_set<int> position;
};

int main()
{
    vector<vector<int>> grid = {
        {1, 0},
        {0, 1}};
    Solution solution{};
    solution.largestIsland(grid);
    return 0;
}